package com.sheng.leetcode.year2023.swordfingerofferspecial.day01;

import org.junit.Test;

/**
 * @author liusheng
 * @date 2023/02/02
 * <p>
 * 剑指 Offer II 001. 整数除法<p>
 * <p>
 * 给定两个整数 a 和 b ，求它们的除法的商 a/b ，要求不得使用乘号 '*'、除号 '/' 以及求余符号 '%' 。<p>
 * 注意：<p>
 * 整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2<p>
 * 假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−2^31, 2^31−1]。本题中，如果除法结果溢出，则返回 2^31 − 1<p>
 * <p>
 * 示例 1：<p>
 * 输入：a = 15, b = 2<p>
 * 输出：7<p>
 * 解释：15/2 = truncate(7.5) = 7<p>
 * <p>
 * 示例 2：<p>
 * 输入：a = 7, b = -3<p>
 * 输出：-2<p>
 * 解释：7/-3 = truncate(-2.33333..) = -2<p>
 * <p>
 * 示例 3：<p>
 * 输入：a = 0, b = 1<p>
 * 输出：0<p>
 * <p>
 * 示例 4：<p>
 * 输入：a = 1, b = 1<p>
 * 输出：1<p>
 * <p>
 * 提示:<p>
 * -2^31 <= a, b <= 2^31 - 1<p>
 * b != 0<p>
 * <p>
 * 注意：本题与主站 29 题相同：<a href="https://leetcode-cn.com/problems/divide-two-integers/">主站29</a><p>
 * <p>
 * 来源：力扣（LeetCode）<p>
 * 链接：<a href="https://leetcode.cn/problems/xoh6Oh">剑指 Offer II 001. 整数除法</a><p>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。<p>
 */
public class Sword001 {

    @Test
    public void test01() {
        int a = 15, b = 2;
//        int a = 7, b = -3;
//        int a = 0, b = 1;
//        int a = 1, b = 1;
        System.out.println(new Solution().divide(a, b));
    }
}

//class Solution {
//    public int divide(int a, int b) {
//        if (a == -2147483648 && b == -1) {
//            return 2147483647;
//        }
//        boolean flag = true;
//        if ((a < 0 && b > 0) || (a > 0 && b < 0)) {
//            flag = false;
//        }
//        a = Math.abs(a);
//        b = Math.abs(b);
//        int ans = 0;
//        while (a >= b) {
//            a -= b;
//            ans++;
//        }
//        if (flag) {
//            return ans;
//        } else {
//            return -ans;
//        }
//    }
//}

class Solution {
    /**
     * 实现整数除法：借鉴乘法的定义，所以除法就是被除数够减去除数几次，那么就商几
     * 但是有几个情况需要考虑（除零不需要考虑，这里已经给我们排除了）
     * 1、同号相除，转为绝对值，结果为正
     * 2、异号相除：转为绝对值，结果为负
     * (1)被除数为正数、除数为负数
     * 将除数转为绝对值，最后结果变为相反数即可
     * (2)被除数为负数、除数为正数
     * 将被除数转为绝对值，最后结果变为相反数即可
     * 3、结果溢出：
     * 什么时候会溢出？也就是-2^31/-1转为正数时溢出，所以我们可以直接判断这个情况就好
     * 2^31=2147483648
     * 4、算子的特殊情况：
     * 被除数为Integer.MIN_VALUE,做一下加分再用abs（）的方法
     * 除数为Integer.MIN_VALUE（排除被除数与除数一致的情况），那么结果肯定是0（因为被除数肯定不够除）
     * 5、不用（*；/）除、乘符号将数字转为自己的相反数
     * 在计算机里按照二进制存储：
     * （1）正数也就是直接原码、补码是一致的
     * （2）负数存储的是补码
     * 例如：
     * 5的原码是0101（其中最高位是符号位0），它的负数在计算机里按补码存储，也就是-5，
     * 首先得到绝对值的原码0101，然后是取反1010（符号位变为1了），最后是加一，变为1011（最高位1是符号位）
     * 可以观察出：5->-5就是原码取反+1，而-5变成5也是取反加一
     * 所以方法就是取反+1即可
     */
    public int divide(int a, int b) {
        if (a == 0) {
            // 0 除以任何数都为 0
            return 0;
        }
        if (b == 1) {
            // 任何数除以 1 都为任何数
            return a;
        }
        if (a == b) {
            //任何数除以自己（ 0 除外）都为 1
            return 1;
        }
        // 保存结果，其实就是记录相减了几次
        int res = 0;
        // 记录有几个值为负数
        int flag = 0;
        // 被除数为最小值，做一下处理
        if (a == Integer.MIN_VALUE) {
            a = a + Math.abs(b);
            res = 1;
        }
        // 除数为最小值，那么肯定为0
        if (b == Integer.MIN_VALUE) {
            return 0;
        }
        if (a < 0) {
            // 转为绝对值
            a = Math.abs(a);
            ++flag;
        }
        if (b < 0) {
            b = Math.abs(b);
            ++flag;
        }
        // 两个特殊情况
        if ((flag == 0 || flag == 2) && b == 1) {
            return a;
        }
        if (flag == 1 && b == 1) {
            a = ~a + 1;
            return a;
        }
        while (a >= b) {
            a -= b;
            // 相减一次，结果加一
            ++res;
        }
        // 这里利用取反操作来将一个正数变为负数：
        if (flag == 1) {
            res = ~res + 1;
        }
        return res;
    }
}
